#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
using namespace std;
typedef struct node
{
	int data;
	struct node *left,*right;
}*BiTree;
BiTree newNode(int data){
    BiTree node=(BiTree)malloc(sizeof(struct node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    return node;
}
BiTree create_bst(BiTree node,int data){//返回插入新节点后的bst树的根节点
    if(node==NULL)
        return newNode(data);
    if(node->data>data)
        node->left=create_bst(node->left,data);
    else
        node->right=create_bst(node->right,data);
    return node;
}
BiTree minValNode(BiTree node){
    if(NULL==node)
        return node;
    BiTree curNode=node;
    while(curNode->left){//这里注意了
        curNode=curNode->left;
    }
    return curNode;
}
/*
*删除某个节点：
*1.叶子节点直接删
*2.要删除的节点只有一个子节点 子节点替，然后删除子节点
*3.要删除的节点有两个子节点 往左找最大或者往右找最小的(中序遍历中待删除节点x的后继y)，按2的方法操作
*@返回值 BiTree 是deleteNode后新树的根节点
*@param root 是每次递归时的节点（初始为原bst树的根节点）
*@param p 是待删除节点
*/
BiTree del(BiTree root,BiTree p){
    if(root==NULL)
        return root;
    if(root->data>p->data)
        root->left=del(root->left,p);
    else if(root->data<p->data)
        root->right=del(root->right,p);
    else{
        //只有一个孩子或者无孩子
        if(root->left==NULL){//1、只有右孩子
            BiTree node=root->right;

            free(node);
            return node;
        }
        if(root->right==NULL){//2、只有左孩子
            BiTree node=root->left;
            free(node);
            return node;
        }
        //两个子节点：这里找右子树的最小值
        BiTree temp=minValNode(root->right);
        root->data=temp->data;//把找到的最小值赋值给待删除节点，转换成1，2去删除
        root->right=del(root->right,temp);
    }
    return root;
}
void getParent(BiTree root,BiTree p,BiTree parent)//找到p的双亲结点
{
	if(root!=NULL)
	{
		if(root->data>p->data)
		{
			parent=root;
			getParent(root->left,p,parent);
		}
		else if(root->data<p->data)
		{
			parent=root;
			getParent(root->right,p,parent);
		}
		else return;
	}
}
void DeleteBTNode(BiTree root,BiTree p)
{
	BiTree parent=NULL;
	getParent(root,p,parent);
	if(p->left==NULL&&p->right!=NULL)//只有右子树
	{
		if(root==p)
		{
			root=p->right;
		}
		else
		{
			if(parent->data>p->data)
				parent->left=p->right;
			else
				parent->right=p->right;
		}
	}
	else if(p->left!=NULL&&p->right==NULL)//只有左子树
	{
		if(root==p)
		{
			root=p->left;
		}
		else
		{
			if(parent->data>p->data)
			{
				parent->left=p->left;
			}
			else
				parent->right=p->left;
		}
	}
	else if(p->left!=NULL&&p->right!=NULL)//有两个孩子
	{
		BiTree temp=p->left;
		while(temp->right!=NULL)//找左子树的最大结点
		{
			temp=temp->right;
		}
		int t2;  //交换temp与p结点的数据
		t2=p->data;
		p->data=temp->data;
		temp->data=t2;
		DeleteBTNode(root,temp);//删除temp
	}
	else //叶结点
	{
		if(parent->data>p->data)
			parent->left=NULL;
		else
			parent->right=NULL;
		free(p);
	}
}
void preOrder(BiTree node){
    if(NULL==node)
        return;
    printf("%d ",node->data);
    preOrder(node->left);
    preOrder(node->right);
}
//删除一个结点(成功返回1，失败返回0)
void BSTreeRemoveR(BiTree* root, BiTree x)
{
    assert(root);
    //树为空，删除失败
    if ((*root) == NULL)
    {
        return;
    }
    //要删除的数小于根结点的数，说明要删除的结点在左树
    if ((*root)->data > x->data)
    {
        BSTreeRemoveR(&(*root)->left, x);
    }
    //要删除的数大于根结点的数，说明要删除的结点在右树
    else if ((*root)->data < x->data)
    {
        BSTreeRemoveR(&(*root)->right, x);
    }
    //*root一定为要删除的结点
    else
    {
        //记录要释放的结点
        BiTree del = *root;
        //1.左子树为空或者右子树为空
        if ((*root)->left == NULL)
        {
            *root = (*root)->right;
            free(del);
        }
        else if ((*root)->right == NULL)
        {
            *root = (*root)->left;
            free(del);
        }
        //2.左右子树都不为空(替换删除法)
        else
        {
            BiTree replace = (*root)->right;//找右子树的最小值代替
            while (replace->left)
            {
                replace = replace->left;
            }
            (*root)->data = replace->data;
            BSTreeRemoveR(&(*root)->right, replace);
        }
    }
}
int main(){
    BiTree root=NULL;
    int arr[7]={10,20,5,24,7,8,6};
    for(int i=0;i<7;i++){
        root=create_bst(root,arr[i]);
    }
    preOrder(root);
    /*
        10
       /  \
      5    20
       \      \
        7      24
       / \
      6   8
    */
    // DeleteBTNode(root,root->left);
    // root=del(root,root->left);
	BSTreeRemoveR(&root,root->left);
    printf("\n删除后:\n");
    preOrder(root);
    return 0;
}